package com.qqn.zcy.class02;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 一个数组中有一种数出现K次，其他数都出现了M次M > 1. K< M找到，出现了K次的数，要求，额外空间复杂度O(1)，时间复杂度O(N)
 */
public class Code03_KM {

    public static HashMap<Integer, Integer> map = new HashMap<>();

    // 请保证 arr 中，只有一种数出现了 K 次，其他数都出现了 M 次

    /**
     *
     * @param arr
     * @param k
     * @param m
     * @return
     */
    public static int onlyKTimes(int[] arr, int k, int m) {
        if (map.isEmpty()) {
            mapCreator(map);
        }

        /**
         *  t 用来模拟32位二进制的数组
         */
        int[] t = new int[32];

        // t[0] 0位置的 1 出现了几个
        // t[i] i位置的 1 出现了几个
        for (int num : arr) { // 拿数组中一个数
            while (num != 0) {
                int rightOne = num & (-num); // 拿到这个数 只有最右侧 1 其他全是0 的二进制数
                // 这里 rightOne 由于是 二进制的指数 因此需要使用 指数映射表处理 比如 0100拿到的就是map中键名为 4 的键值对 其值为 3 也就是 t 的第三位上需要 +1 表示这个数在这个位上有 1
                t[map.get(rightOne)]++; // 将这个32位的二进制数对应的位置加一 表示当前的数在这一位有 1
                num ^= rightOne;  // 消掉当前 num 最右侧的 1， 暴露出更高一位最右侧为 1 的位 让下次循环的时候 rightOne继续获取，这样就能将这个数以二进制的形式存储在这个32长度的数组中
                // 0111000 ^ 0001000 --> 0110000
            }
        }
        /**
         * ans 出现次数为 k 次的数(操作二进制)
         */
        int ans = 0;
        for (int i = 0; i < 32; i++) { // 遍历组装好的模拟二进制的数组
            if (t[i] % m != 0) {  // 这个条件判断无法判断到 0的二进制 需要对0这个数进行特殊处理(补丁)
                // 进入这里说明 当前位 有出现 k 次的数的二进制 1
                if (t[i] % m == k) {
                    // 进入这里说明刚好这个 k 在这里有 1 将他的二进制位 1 写入到 ans 对应的位中
                    ans |= (1 << i);
                } else {
                    // 进入这里说明 有出现次数既不是 M 次的也不是 K 次的数  返回 -1
                    return -1;
                }
            }
        }
        // 如果是 0 这个数 需要特殊处理
        if (ans == 0) {
            int count = 0;
            for (int num : arr) {
                if (num == 0) {
                    count++;
                }
            }
            if (count != k) {
                // 出现次数不是 k 说明存在一个数出现次数不为 k 次的情况 结束方法
                return -1;
            }
        }

        return ans;  // 出现 k 次的数
    }

    // for test   HashMap 做计数器 计算每个数出现的次数
    public static int test(int[] arr, int k, int m) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                return num;
            }
        }
        return -1;
    }

    // 创建指数和位数的映射表  用于往模拟的32位二进制数组的指定位中添加计数
    public static void mapCreator(HashMap<Integer, Integer> map) {
        int value = 1;
        for (int i = 0; i < 32; i++) {
            map.put(value, i); // i  0 1 2 3 4 ...
            value <<= 1;  // value  1 2 4 8 16 32 ...
        }
    }

    /**
     * 生成要进行查询的数组
     * @param maxKinds 最大次数
     * @param range  随机数生成范围
     * @param k  k 次
     * @param m  m 次
     * @return  返回要查询的数组
     */
    public static int[] randomArray(int maxKinds, int range, int k, int m) {
        int ktimeNum = randomNumber(range);
        // 真命天子出现的次数  要么就是 k 次 要么就出现小于 m 次 设置概览产生出现次数不为m也不为k次的数
        int times = Math.random() < 0.5 ? k : ((int) (Math.random() * (m - 1)) + 1);
        // 2  全部数的种类  +2 防止出现次数小于2
        int numKinds = (int) (Math.random() * maxKinds) + 2;
        // k * 1 + (numKinds - 1) * m
        int[] arr = new int[times + (numKinds - 1) * m]; // 存的 十进制数的个数 times + (numKinds - 1) * m  要往这个数组中存所有的十进制数
        // 先存出现 k 次的数
        int index = 0;
        for (; index < times; index++) {
            arr[index] = ktimeNum; // 存储 k 次数的数
        }
        numKinds--;  // 总种类减去 k次出现的数的这一种
        HashSet<Integer> set = new HashSet<>();
        set.add(ktimeNum);  // 将出现 k 次的数存入 Set 集合中 防止在生成重复的数
        while (numKinds != 0) {
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            } while (set.contains(curNum)); // 确保拿到不重复的数
            set.add(curNum);
            numKinds--;
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum; // 先赋值再自增
            }
        }
        // 填好了
        for (int i = 0; i < arr.length; i++) {
            // i 位置的数，我想随机和 j 位置的数做交换
            int j = (int) (Math.random() * arr.length); // 0 ~ N-1
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        return arr;
    }

    /**
     * 产生随机数
     *
     * @param range
     * @return
     */
    // [-range, +range]
    public static int randomNumber(int range) {
        return ((int) (Math.random() * range) + 1) - ((int) (Math.random() * range) + 1);
    }

    public static void main(String[] args) {
        int kinds = 5; // 一共存在的数字种类种数
        int range = 30;
        int testTime = 100000;
        int max = 9;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int a = (int) (Math.random() * max) + 1; // 1 ~ 9
            int b = (int) (Math.random() * max) + 1; // 1 ~ 9
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            // k < m
            if (k == m) {
                m++;
            }
            int[] arr = randomArray(kinds, range, k, m);
            int ans1 = test(arr, k, m);
            int ans2 = onlyKTimes(arr, k, m);
            if (ans1 != ans2) {
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("出错了！");
            }
        }
        System.out.println("测试结束");
    }
}
